package solution2.year_2024;


import java.net.Inet4Address;
import java.util.*;
import java.util.stream.Stream;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution1 {

    //1.移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    //3.反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curNext = cur.next;
        cur.next = null;
        while(curNext != null) {
            ListNode curNextNext = curNext.next;
            curNext.next = cur;
            cur = curNext;
            curNext = curNextNext;
        }
        return cur;
    }

    //4.删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prev = getToDelListNodePrev(dummy, head, n);
        toDel(prev);
        return dummy.next;
    }

    private void toDel(ListNode prev) {
        ListNode del = prev.next;
        prev.next = del.next;
        del.next = null;
    }

    private ListNode getToDelListNodePrev(ListNode dummy, ListNode head, int n) {
        ListNode prev = dummy;
        ListNode fast = head;
        ListNode slow = head;
        while(n > 0) {
            fast = fast.next;
            n--;
        }
        while(fast != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        return prev;
    }

    //5.两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curLeft = head;
        ListNode curRight = head.next;
        while(curLeft != null && curLeft.next != null) {
            ListNode newStart = curRight.next;
            prev.next = curRight;
            curRight.next = curLeft;
            curLeft.next = newStart;
            prev = curLeft;
            curLeft = newStart;
            if(curLeft == null) {
                break;
            }
            curRight = curLeft.next;
        }
        return dummy.next;
    }

    //6.面试题 02.07. 链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != null) {
            curA = curA.next;
            lenA++;
        }
        while(curB != null) {
            curB = curB.next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        ListNode intersection = null;
        if(lenA > lenB) {
            intersection = getIntersection(lenA - lenB, curA, curB);
        } else {
            intersection = getIntersection(lenB - lenA, curB, curA);
        }
        return intersection;
    }

    private ListNode getIntersection(int ans, ListNode fast, ListNode slow) {
        while(ans > 0) {
            fast = fast.next;
            ans--;
        }
        while(fast != null && fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    //7.环形链表 II
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while(fast != null && fast.next != null && slow != null && fast != slow) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        ListNode cur = head;
        while(cur != fast) {
            cur = cur.next;
            fast = fast.next;
        }
        return cur;
    }

    //8.重排链表
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) {
            return;
        }
        //分割链表
        ListNode mid = splitList(head);
        //反转链表
        ListNode cur2 = reverseList(mid);
        //拼接链表
        mergeList(head, cur2);
    }

    private void mergeList(ListNode cur1, ListNode cur2) {
        while(cur1 != null && cur2 != null) {
            ListNode cur1Next = cur1.next;
            ListNode cur2Next = cur2.next;
            if(cur1.next == null) {
                cur1.next = cur2;
                return;
            }
            cur1.next = cur2;
            cur2.next = cur1Next;
            cur1 = cur1Next;
            cur2 = cur2Next;
        }
    }

    private ListNode splitList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode mid = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            mid = slow;
            slow = slow.next;
        }
        mid.next = null;
        return slow;
    }

    //9.有效的字母异位词
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        int lenS = s.length();
        int lenT = t.length();
        if(lenS != lenT) {
            return false;
        }
        for(int i = 0; i < lenS; i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1);
        }
        for(Map.Entry<Character, Integer> entry : map.entrySet()) {
            if(entry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }

    //10.两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] nums = new int[1001];
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums1.length; i++) {
            if(nums[nums1[i]] == 0) {
                nums[nums1[i]]++;
            }
        }
        for(int i = 0; i < nums2.length; i++) {
            if(nums[nums2[i]] != 0) {
               list.add(nums2[i]);
               nums[nums2[i]]--;
            }
        }
        int[] result = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    //11.快乐数
    //2 4 16 37 58 89 145 42 2
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n != 1) {
            if(set.contains(n)) {
                return false;
            }
            set.add(n);
            int tmp = n;
            int sum = 0;
            while(tmp != 0) {
                sum += ((tmp % 10) * (tmp % 10));
                tmp /= 10;
            }
            n = sum;
        }
        return true;
    }

    //12
    public int[] twoSum(int[] nums, int target) {
        //key: 值, value: 下标
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                result[0] = i;
                result[1] = map.get(target - nums[i]);
                return result;
            }
            map.put(nums[i], i);
        }
        return result;
    }

    //13
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //key: 两数和, value: 出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int num1 : nums1) {
            for(int num2 : nums2) {
                 map.put(num1 + num2, map.getOrDefault(num1 + num2, 0) + 1);
            }
        }
        int result = 0;
        for(int num3 : nums3) {
            for(int num4 : nums4) {
                if(map.containsKey(-(num3 + num4))) {
                    result += map.get(-(num3 + num4));
                }
            }
        }
        return result;
    }

    //14
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        if(nums[0] > 0) {
            return result;
        }
        for(int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) {
                    right--;
                } else if(sum < 0) {
                    left++;
                } else {
                    result.add(List.of(nums[i], nums[left], nums[right]));
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }

    //15.
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 1; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for(int j = i + 1; j < nums.length; j++) {
                if(j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while(left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target) {
                        left++;
                    } else if(sum > target) {
                        right--;
                    } else {
                        result.add(List.of(nums[i], nums[j], nums[left], nums[right]));
                        while(left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        long num =  (long)1000000000 + 1000000000 + 1000000000 + 1000000000;
        System.out.println(num);

//        int[] nums = {1,-2,-5,-4,-3,3,3,5};
//        Solution1 solution1 = new Solution1();
//        solution1.fourSum(nums, -11);
    }

}

//2
class MyLinkedList {

    static class ListNode {
        private int val;
        private ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode dummy;
    private int length;

    public MyLinkedList() {
         this.dummy= new ListNode();
         this.length = 0;
    }

    public int get(int index) {
        if(index >= length)  {
            return -1;
        }
        ListNode cur = dummy.next;
        while(index > 0) {
            index--;
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        ListNode prev = this.dummy;
        ListNode cur = prev.next;
        prev.next = node;
        node.next = cur;
        length++;
    }

    public void addAtTail(int val) {
        ListNode cur = this.dummy;
        while(cur.next != null) {
            cur = cur.next;
        }
        ListNode node = new ListNode(val);
        cur.next = node;
        length++;
    }

    public void addAtIndex(int index, int val) {
        if(index > length) {
            return;
        }
        ListNode prev = this.dummy;
        ListNode cur = this.dummy.next;
        while(index > 0) {
            index--;
            prev = cur;
            cur = cur.next;
        }
        ListNode node = new ListNode(val);
        prev.next = node;
        node.next = cur;
        length++;
    }

    public void deleteAtIndex(int index) {
        if(index >= length) {
            return;
        }
        ListNode prev = this.dummy;
        ListNode cur = prev.next;
        while (index > 0) {
            index--;
            prev = cur;
            cur = cur.next;
        }
        prev.next = cur.next;
        cur = null;
        length--;
    }

}

class Main {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addAtHead(7);
        list.addAtHead(2);
        list.addAtHead(1);
        list.addAtIndex(3, 0);
        list.deleteAtIndex(2);
        list.addAtHead(6);
        list.addAtTail(4);
        list.get(4);
    }
}
